◀ Prev · Parts · Full · Next ▶

Any Boolean function f ( x ) : { 0 , 1 } n → → { 0 , 1 } {\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}} can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in R n {\displaystyle \mathbb {R} ^{n}} , constructed by summing the truth table values multiplied by indicator polynomials: f ∗ ∗ ( x ) = ∑ ∑ a ∈ ∈ { 0 , 1 } n f ( a ) ∏ ∏ i : a i = 1 x i ∏ ∏ i : a i = 0 ( 1 − − x i ) {\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})} For example, the extension of the binary XOR function x ⊕ ⊕ y {\displaystyle x\oplus y} is 0 ( 1 − − x ) ( 1 − − y ) + 1 x ( 1 − − y ) + 1 ( 1 − − x ) y + 0 x y {\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy} which equals x + y − − 2 x y {\displaystyle x+y-2xy} Some other examples are negation ( 1 − − x {\displaystyle 1-x} ), AND ( x y {\displaystyle xy} ) and OR ( x + y − − x y {\displaystyle x+y-xy} ). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated modulo 2 one obtains the algebraic normal form (Zhegalkin polynomial).

◀ Prev · Parts · Full · Next ▶